#-*- encoding:utf-8 -*-

#1. 暴力查找法，扫描两数组，找他们一样的，找过的就跳过O(n^2) 提高效率就是对数组2进行排序
#2. 对数组都进行排序，再用两个指针进行扫描
#3. hashmap O(n)
#4. 集合求交集

def intersection(nums1, nums2):
	res = []
	dict = {}
	for x in nums1:
		if dict.has_key(x) is False:
			dict[x] = 1
		else:
			dict[x] +=1

	for x in nums2:
		if dict.has_key(x) and dict[x] > 0:
			res.append(x)
			dict[x] = 0
	return res



num1 = [1,2,2,1,5,6,7,5]
num2 = [2,2,4,5]
print intersection(num1,num2)